Codeforces Round #818 (Div. 2)

A

不妨设 $a\le b,\,d=\gcd(a,b)$ 。

令 $a=da_1,\,b=db_1$ ，且 $\gcd(a_1,b_1)=1$ 。

则 $\operatorname{lcm}(a,b)=da_1b_1$ 。

从而 $\dfrac{\operatorname{lcm}(a,b)}{\gcd(a,b)}=a_1b_1\le 3$ ，一共只有 $3$ 种情况，讨论一下即可。

Code

#include <cstdio>

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        printf("%d\n", (n / 2 + n / 3) * 2 + n);
    }
}

B

容易发现排列是有周期性的，只需要处理 $k\times k$ 的方格表，循环输出即可。

Code

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 505;

char mp[N][N];
int T, n, k, r, c;

void solve() {
    scanf("%d%d%d%d", &n, &k, &r, &c);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            mp[i][j] = '.';
    }
    r = (r - 1) % k + 1;
    c = (c - 1) % k + 1;
    for (int i = 1; i <= k; i++) {
        mp[r--][c++] = 'X';
        if (r == 0) r = k;
        if (c == k + 1) c = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            putchar(mp[(i - 1) % k + 1][(j - 1) % k + 1]);
        puts("");
    }
}

int main() {
    scanf("%d", &T);
    while (T--) solve();
}

C

后面我都不会做了

首先必须要求 $b_i\ge a_i$ ，否则必然不可行。

由于数列是环状的，不妨破环成链，令 $a_{n+1}=a_1,\,b_{n+1}=b_1$ 。

结论：$a$ 能变换到 $b$ 等价于对于任意 $i$ ，有 $a_i=b_i$ 或 $b_i\le b_{i+1}+1$ 。

先证充分性。考虑将 $a_i$ 变换至 $b_i$ 的最后一次操作，若 $a_i=b_i$ 则不用变换，否则必然是 $a_i=b_i-1$ 且 $a_{i+1}\le b_{i+1}$ 。

由于此时 $a_i\le a_{i+1}$ ，故有

$b_i-1\le a_{i+1}\le b_{i+1}$

从而 $b_i\le b_{i+1}+1$ 。

再证必要性。考虑每一轮变换 $a_i=\min\limits_{j}{a_j}$ ，则 $a_i \lt b_i \le b_{i+1}+1$ ，故我们必然可以让 $a_i$ 进行一次变换，易知可以持续操作直至 $a=b$ 。

所以只需要判断两种情况即可，时间复杂度 $O(\sum n)$ 。

Code

#include <cstdio>
#include <cstring>

const int N = 4e5 + 5;

int a[N], b[N], n, T;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            a[i + n] = a[i];
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);
            b[i + n] = b[i];
        }
        bool flag = 1;
        for (int i = 1; i <= n; i++) {
            if (b[i] < a[i])
                flag = 0;
        }
        if (!flag) {
            puts("NO");
            continue;
        }
        flag = 1;
        for (int i = 1; i <= n; i++) {
            if (b[i] > b[i + 1] + 1 && a[i] != b[i])
                flag = 0;
        }
        puts(flag ? "YES" : "NO");
    }
}

D

以下内容来源于题解

考虑对于每个人到根节点的路径，将每条边的胜负分别对应 $1/0$ ，得到一个长度为 $n$ 的二进制数，可以证明这样的 $2^n$ 个二进制数和树上 $2^n$ 个叶节点一一对应，不妨设 $f(x)$ 表示叶节点 $x$ 对应的二进制数。

我们考虑判断某个节点 $u$ 是否可以通过不超过 $k$ 调整使得 $u$ 最终获胜，即每次在 $f(u)$ 中修改一位的值，最终能否使 $f(u)$ 全部为 $1$ ，不难发现这个问题等价于使得 $f(u)$ 中的 $0$ 的个数不超过 $k$ ，显然，最终状态就是所有这样的 $u$ 的最大值。

注意到所有 $f$ 值中有 $i$ 位为 $0$ 的有 $\binom{n}{i}$ 个，即答案为

$\sum\limits_{i=0}^{\min\{n,k\}}\dbinom{n}{i}$

时间复杂度 $O(\min\{n,k\})$ 。

Code

#include <algorithm>
#include <iostream>
using namespace std;

typedef long long int64;

const int N = 1e5 + 5;
const int64 mod = 1e9 + 7;

int64 fac[N], inv[N], n, k, ans;

inline int64 pow(int64 a, int64 b) {
    int64 res = 1;
    for (; b; b >>= 1, a = a * a % mod) if (b & 1) res = res * a % mod;
    return res;
}

int64 binom(int64 x, int64 y) {
    return 1LL * fac[x] * inv[y] % mod * inv[x - y] % mod;
}

int main() {
    cin >> n >> k;
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = pow(fac[i], mod - 2);
    }
    for (int i = 0; i <= min(n, k); i++) ans = (ans + binom(n, i)) % mod;
    cout << ans << endl;
}

E

考虑枚举 $c$ ，此时有

$\gcd(a,b)=\gcd(a,a+b)=\gcd(a,n-c)$

令 $d=\gcd(a,b)$ ，则 $d$ 为 $n-c$ 的约数。

设 $a=da_1,\,b=db_1$ ，且 $\gcd(a_1,b_1)=1$ ，则 $a+b=d(a_1+b_1)$ ，易知 $\gcd(d,a_1+b_1)=1$ ，从而满足要求的数对 $(a,b)$ 的个数为 $\varphi(\frac{n-c}{d})$ 。

于是答案为

$\sum\limits_{c=1}^{n-2}\sum\limits_{d\mid (n-c)}\operatorname{lcm}(c,d)\times\varphi\left(\frac{n-c}{d}\right)$

预处理 $10^5$ 以内每个数的 $\varphi$ 值和所有约数，时间复杂度 $O(n\log{n})$ 。

Code

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int prime[N], vis[N], phi[N], n, cnt, ans;

inline void sieve() {
    vis[1] = 1;
    for (int i = 2; i < N; i++) {
        if (vis[i] == 0) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] < N; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j]) {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            } else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

vector<int> f[N];

void factor() {
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j += i)
            f[j].push_back(i);
    }
}

int main() {
    scanf("%d", &n);
    sieve();
    factor();
    for (int c = 1; c <= n - 2; c++)
        for (int d: f[n - c]) {
            int lcm = 1LL * c * d / gcd(c, d) % mod;
            ans = (ans + 1LL * lcm * phi[(n - c) / d] % mod) % mod;
        }
    printf("%d\n", ans);
}

F

待补。